﻿//// NC51 合并k个已排序的链表
//// https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=196&tqId=37081&ru=/exam/oj
//
///**
// * struct ListNode {
// *  int val;
// *  struct ListNode *next;
// *  ListNode(int x) : val(x), next(nullptr) {}
// * };
// */
//
// // 暴力解法：排序的写法
//#include <list>
//bool operator<(const ListNode& l1, const ListNode& l2)
//{
//    return l1.val < l2.val;
//}
//
//class Solution {
//public:
//    void dfs(vector<ListNode*>& lists)
//    {
//        sort(lists.begin(), lists.end(), [](ListNode* l1, ListNode* l2) {
//            if (!l1)// l2小
//                return false;
//            else if (!l2)
//                return true;
//            return *l1 < *l2; // 使用重载的 < 运算符
//            });
//        if (!lists[0])
//            return;
//        cout << lists[0]->val << ' ';
//        ListNode* temp = lists[0]->next;
//
//        lists[0]->next = nullptr;
//        p->next = lists[0];
//        p = p->next;
//
//        lists[0] = temp;
//        dfs(lists);
//    }
//
//    ListNode* mergeKLists(vector<ListNode*>& lists)
//    {
//        if (lists.size() == 0)
//            return nullptr;
//        else if (lists.size() == 1)
//            return lists[0];
//
//        dfs(lists);
//        return ans->next;
//    }
//private:
//    ListNode* ans = new ListNode(0);
//    ListNode* p = ans;
//};
//
//// 暴力解法优化：最小堆的写法
///*
//比较函数 堆类型   队首元素    排序顺序
//less<T>      最大堆   最大元素    降序
//greater<T>   最小堆   最小元素    升序
//*/
//#include <list>
//#include <queue>
//#include <vector>
//
//struct Compare {
//    bool operator()(ListNode* l1, ListNode* l2) {
//        if (!l1)// l1大
//            return true;
//        else if (!l2)
//            return false;
//        return l1->val > l2->val; // 小顶堆
//    }
//};
//
//// bool operator<(const ListNode& l1, const ListNode& l2)
//// {
////     return l1.val < l2.val;
//// }
//
//class Solution {
//public:
//    void dfs(priority_queue<ListNode*, vector<ListNode*>, Compare>& pq)
//    {
//        ListNode* top = pq.top();
//        if (!top)
//            return;
//        pq.pop();
//        pq.push(top->next);
//
//        cout << top->val << ' ';
//
//        top->next = nullptr;
//        p->next = top;
//        p = p->next;
//
//        dfs(pq);
//    }
//
//    ListNode* mergeKLists(vector<ListNode*>& lists)
//    {
//        if (lists.size() == 0)
//            return nullptr;
//        else if (lists.size() == 1)
//            return lists[0];
//
//        for (auto& l : lists)
//            pq.push(l);
//        dfs(pq);
//        return ans->next;
//    }
//private:
//    ListNode* ans = new ListNode(0);
//    ListNode* p = ans;
//    priority_queue<ListNode*, vector<ListNode*>, Compare>pq;
//
//    // 不可以用Lambda，因为Lambda是匿名函数，不能作为模板参数传递
//    // priority_queue<ListNode*, vector<ListNode*>, [](ListNode* l1, ListNode* l2)
//    // {
//    //      if (!l1)// l2小
//    //             return false;
//    //         else if (!l2)
//    //             return true;
//    //         return *l1 < *l2; // 使用重载的 < 运算符
//    // }>pq;
//};
//
//
//// 比特答案
///**
//* struct ListNode {
//*  int val;
//*  struct ListNode *next;
//*  ListNode(int x) : val(x), next(nullptr) {}
//* };
//*/
//class Solution {
//    struct cmp {
//        bool operator()(ListNode* l1, ListNode* l2) {
//            return l1->val > l2->val;
//        }
//    };
//public:
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        priority_queue<ListNode*, vector<ListNode*>, cmp> heap; // ⼩根堆
//        for (auto head : lists) {
//            if (head != nullptr) {
//                heap.push(head);
//            }
//        }
//        ListNode* ret = new ListNode(0);
//        ListNode* prev = ret;
//        while (heap.size()) {
//            ListNode* t = heap.top();
//            heap.pop();
//            prev = prev->next = t;
//            if (t->next != nullptr) {
//                heap.push(t->next);
//            }
//        }
//        return ret->next;
//    }
//};